package com.wfs.suanfa.leet;

/**
 * 红黑树
 * 1.创建RBTree，定义颜色
 * 2.创建RBNode
 * 3.辅助方法定义: parentOf(node),isRead(node),isBlack(node),setRed(node),isOrderPrint()
 * 4.左旋方法
 * 5.右旋转方法
 * 6.公开插入接口方法 insert(k,v)
 * 7.内部插入方法
 * 8.修订插入导致红黑树失衡的方法定义 insertFIxUp(RBNode node)
 * 9.测试红黑树正确
 */
public class RBTree<K extends  Comparable<K>,V> {
    private static final boolean RED=true;
    private static final boolean BLACK=false;
    public static class RBNode<K extends  Comparable<K>,V> {
        private RBNode parent;
        private RBNode left;
        private  RBNode right;
        private boolean color;
        private K key;
        private V vaule;

        public RBNode(RBNode parent, RBNode left, RBNode right, boolean color, K key, V vaule) {
            this.parent = parent;
            this.left = left;
            this.right = right;
            this.color = color;
            this.key = key;
            this.vaule = vaule;
        }



        public RBNode() {
        }

        public RBNode getParent() {
            return parent;
        }

        public void setParent(RBNode parent) {
            this.parent = parent;
        }

        public RBNode getLeft() {
            return left;
        }

        public void setLeft(RBNode left) {
            this.left = left;
        }

        public RBNode getRight() {
            return right;
        }

        public void setRight(RBNode right) {
            this.right = right;
        }

        public boolean isColor() {
            return color;
        }

        public void setColor(boolean color) {
            this.color = color;
        }

        public K getKey() {
            return key;
        }

        public void setKey(K key) {
            this.key = key;
        }

        public V getVaule() {
            return vaule;
        }

        public void setVaule(V vaule) {
            this.vaule = vaule;
        }
    }
    /**
     * 树根的引用
     */
    private RBNode root;

    /**
     * 获取当前父节点
     * @param node
     */
    private RBNode  parentOf(RBNode node){
        if (node!=null){
            return node.parent;
        }
        return null;
    }
    /**
     * 是否为红色
     */
    private boolean  isRed(RBNode node){
        if (node!=null){
            return node.color==RED;
        }
        return false;
    }
    /**
     * 是否为黑色
     */
    private boolean  isBlack(RBNode node){
        if (node!=null){
            return node.color==BLACK;
        }
        return false;
    }
    /**
     * 设置红色
     */
    private void  setRed(RBNode node){
        if (node!=null){
            node.color=RED;
        }
    }
    /**
     * 设置黑色
     */
    private void  setBlack(RBNode node){
        if (node!=null){
            node.color=BLACK;
        }
    }

    /**
     * 中序打印二叉树
     */
    public  void inOrderPrint(){
        inOrderPrint(this.root);
    }
    public  void inOrderPrint(RBNode root){
        if (root!=null){
            inOrderPrint(root.left);
            System.out.println("key:"+root.key+",valuel:"+root.vaule);
            inOrderPrint(root.right);
        }
    }

    /**
     * 左旋方法
     * 左旋示意图 左旋X节点
     *      P               P
     *      |               |
     *      X               y
     *     / \   --->     /  \
     *    lx  y          X    ry
     *       /\         / \
     *      ly ry      lx  ly
     * 1.将x的右子节点 指向y的左子节点
     * 2.当x的父节点不为空时，更新y的父节点为x父节点，并将x的节点 指定子树  指定为y
     * 3.将x树父节点位置更新为y， 将y的左子节点更新为x
     *
     *
     */
    private void leftRotate(RBNode x){
        RBNode y = x.right;
        //1.将x的右子节点 指向y的左子节点
        x.right=y.left;
        if (y.left!=null){
            y.left.parent=x;
        }
        //2.当x的父节点不为空时，更新y的父节点为x父节点，并将x的节点 指定子树  指定为y
        if (x.parent!=null){
            y.parent=x.parent;
            //将其x父节点的左 或右 子树位置更新为 y
            if (x==x.parent.left){
                x.parent.left=y;
            }else {
                x.parent.right=y;
            }
        }else {
            this.root=y;
            this.root.parent=null;
        }
        //3.将x树父节点位置更新为y， 将y的左子节点更新为x
        x.parent=y;
        y.left=x;
    }
    /**
     * 右旋
     * 右旋 右旋y节点
     *      P               P
     *      |               |
     *      Y              X
     *     / \   --->     /  \
     *     X   ry        lx   Y
     *   /\                  / \
     *  lx ly               ly  ry
     *
     *  1.将 y的左子节点指向x的右子节点，并且更新x的右子节点为y
     *  2.Y的父节点不为空的时候 更新x的父节点为y父节点，更新y的父节点的指定节点位置为x
     *  3.将Y的父节点更新为 x,将y的左子节点更新为x的右子节点
     */
    private void rightRotate(RBNode y){
        RBNode x = y.left;
        //1.将 y的左子节点指向x的右子节点，并且更新x的右子节点为y
        y.left=x.right;
        if (x.right!=null){
            x.right.parent=y;
        }
        // 2.Y的父节点不为空的时候 更新x的父节点为y父节点，更新y的父节点的指定节点位置为x
        if (y.parent!=null){
            x.parent=y.parent;
            if (y.parent.left==y){
                y.parent.left=x;
            }else {
                y.parent.right=x;
            }
        }else {
            this.root=x;
            this.root.parent=null;
        }
        //3.将Y的父节点更新为 x,将y的左子节点更新为x的右子节点
        y.parent=x;
        x.right=y;
    }
    /**
     * 公开的插入方法
     */
    public void insert(K key,V value){
        RBNode rbNode=new RBNode();
        rbNode.setKey(key);
        rbNode.setVaule(value);
        //新节点一定为红色
        rbNode.setColor(RED);
        insert(rbNode);
    }

    /**
     * 内部有的插入方法
     */
    private void insert(RBNode node){
       //第一步 查看当前节点 node的父节点
        RBNode parent=null;
        RBNode x=this.root;
        while (x!=null){
           parent=x;
           //cmp>0 说明node.key大于 x.key,需要将到x的右子树查找
            // cmp>==0  说明node.key等于 x.替换操作
            //cmp<0 说明node.key大于 x.key,需要将到x的左子树查找
           int cmp=node.key.compareTo(x.key);
            if (cmp>0) {
                x=x.right;
            }else if (cmp==0){
                x.setVaule(node.getVaule());
                return;
            }else {
                x=x.left;
            }
        }
        node.parent=parent;
        if (parent!=null){
            int cmp=node.key.compareTo(parent.key);
            if (cmp>0) {
                parent.right=node;
            }else {
                parent.left=node;
            }
        }else {
            this.root=node;
            this.root.parent=null;
        }
        //修复红黑树平衡问题
        insertFIxUp(node);
    }
    /**
     * 插入后修复红黑树平衡的方法
     * 情景
     * 1.为空树 将根节点设置为黑色
     * 2.插入节点key存在 不做处理
     * 3.插入节点的父亲节点为黑色 黑色节点无变化 直接做插入
     *
     *
     * 4.其他情况
     *      1.插入节点的父亲节点为红色·
     *          1.1:叔叔节点存在，并且为红色 叔父 双红
     *              处理:将叔父节点染色为黑色，将爷爷染色为红色，并且再以爷爷为当前节点进行下一轮处理
     *          1.2 叔叔节点不存在或者为黑色，父亲为爷爷节点的左子树
     *              1.2.1:插入节点为其父亲的左子节点(LL情况)
     *                  处理:将父亲节点染色为黑色，爷爷节点染色为红色，然后以爷爷节点右旋
     *              1,2.2:插入节点的为父亲的右子节点(LR情况)
     *                    处理:以父亲节点进行一次左旋得到 LL双红情况，然后指定父亲节点为当前节点进行下一轮 处理
     *         1.3.叔叔节点不存在或者为黑色，父亲为爷爷节点的右子树
     *              1.3.1:插入节点的为父亲的右子节点(RR情况)
     *                   处理:将父亲节点染色为黑色爷爷节点变红，对爷爷节点进行左旋
     *              1.3.2:插入节点为其父亲的左子节点(RL情况)
     *                  处理:将父亲节点进行一次右旋等到 (RR双红情况)，然后以父亲节点为当前节点进行下一轮处理
     */
    private void insertFIxUp(RBNode node){
        this.root.setColor(BLACK);
        RBNode parnet=parentOf(node);
        RBNode gparnet=parentOf(parnet);
        //插入节点的父亲节点为红色·
        if (parnet!=null && isRed(parnet)){
            //如果父节点为红色 一定有爷爷节点，因为根节点不可能为红
            RBNode uncle=null;
            //插入节点 父亲为左子树
            if (parnet==gparnet.left){
                uncle=gparnet.right;
                //4.1.1:叔叔节点存在，并且为红色 叔父 双红
                if (uncle!=null && isRed(uncle)){
                    // 处理:将叔父节点染色为黑色，将爷爷染色为红色，并且再以爷爷为当前节点进行下一轮处理
                   setBlack(parnet);
                   setBlack(uncle);
                   setRed(gparnet);
                   insertFIxUp(gparnet);
                   return;
                }
                // 4.1.2 叔叔节点不存在或者为黑色，
                if (uncle==null || isBlack(uncle)){
                    //4 1.2.1:插入节点为其父亲的左子节点(LL情况)
                    //  处理:将父亲节点染色为黑色，爷爷节点染色为红色，然后以爷爷节点右旋
                    if (node==parnet.left){
                        setBlack(parnet);
                        setRed(gparnet);
                        rightRotate(gparnet);
                        return;
                    }
                    //4 1,2.2:插入节点的为父亲的右子节点(LR情况)
                    //处理:以父亲节点进行一次左旋得到 LL双红情况，然后指定父亲节点为当前节点进行下一轮 处理
                    if (node==parnet.right){
                        leftRotate(parnet);
                        insertFIxUp(parnet);
                        return;
                    }

                }
            }else {
                uncle=gparnet.left;
                //处理:将叔父节点染色为黑色，将爷爷染色为红色，并且再以爷爷为当前节点进行下一轮处理
                if (uncle!=null && isRed(uncle)){
                    // 处理:将叔父节点染色为黑色，将爷爷染色为红色，并且再以爷爷为当前节点进行下一轮处理
                    setBlack(parnet);
                    setBlack(uncle);
                    setRed(gparnet);
                    insertFIxUp(gparnet);
                    return;
                }
                //  1.3.叔叔节点不存在或者为黑色
                if (uncle==null || isBlack(uncle)){
                    //4 1.3.1:插入节点的为父亲的右子节点(RR情况)
                    // 处理:将父亲节点染色为黑色爷爷节点变红，对爷爷节点进行左旋
                    if (node==parnet.right){
                        setBlack(parnet);
                        setRed(gparnet);
                        leftRotate(gparnet);
                        return;
                    }
                    //4 1.3.2:插入节点为其父亲的左子节点(RL情况)
                    //  处理:将父亲节点进行一次右旋等到 (RR双红情况)，然后以父亲节点为当前节点进行下一轮处理
                    if (node==parnet.left){
                        rightRotate(parnet);
                        insertFIxUp(parnet);
                        return;
                    }
                }


            }
        }

    }

    public RBNode getRoot() {
        return root;
    }


}
